﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Hashs
{
    class HashTest
    {
        public static void Test()
        {
            var hashTable = new HashTable<int, int>(2);
            hashTable.Insert(1, 11);
            hashTable.Insert(2, 22);
            hashTable.Insert(3, 33);
            hashTable.Insert(4, 44);

            int value;
            hashTable.Find(1, out value);
            Console.WriteLine(value);
            hashTable.Find(2, out value);
            Console.WriteLine(value);
            hashTable.Find(3, out value);
            Console.WriteLine(value);
            hashTable.Find(4, out value);
            Console.WriteLine(value);
        }

        class Node<TKey, TValue>
        {
            public TKey Key { get; set; }

            public TValue Value { get; set; }

            public Node<TKey, TValue> Next { get; set; }
        }

        class LinkedList<TKey, TValue>
        {
            public Node<TKey, TValue> First { get; set; }

            public void Insert(TKey key, TValue value)
            {
                if (this.Contains(key))
                {
                    throw new InvalidOperationException("不能插入重复的键");
                }

                var node = new Node<TKey, TValue> { Key = key, Value = value };
                node.Next = this.First;
                this.First = node;
            }

            public void Delete(TKey key)
            {
                Node<TKey, TValue> parent;
                Node<TKey, TValue> node;

                if (!this.Find(key, out   parent, out  node))
                {
                    throw new InvalidOperationException("不存在指定的键");
                }

                if (parent == null)
                {
                    this.First = null;
                }
                else
                {
                    parent.Next = node.Next;
                }
            }

            public bool Contains(TKey key)
            {
                Node<TKey, TValue> parent;
                Node<TKey, TValue> node;

                return this.Find(key, out   parent, out  node);
            }

            public bool Find(TKey key, out Node<TKey, TValue> node)
            {
                Node<TKey, TValue> parent;

                return this.Find(key, out  parent, out  node);
            }

            public bool Find(TKey key, out Node<TKey, TValue> parent, out Node<TKey, TValue> node)
            {
                parent = null;
                node = this.First;

                while (node != null)
                {
                    if (node.Key.Equals(key))
                    {
                        return true;
                    }

                    parent = node;
                    node = node.Next;
                }

                return false;
            }
        }

        class HashTable<TKey, TValue>
        {
            private LinkedList<TKey, TValue>[] _items;

            public HashTable(int size)
            {
                _items = new LinkedList<TKey, TValue>[size];
            }

            public void Insert(TKey key, TValue value)
            {
                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    _items[index] = new LinkedList<TKey, TValue>();
                }

                _items[index].Insert(key, value);
            }

            public void Delete(TKey key)
            {
                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    throw new InvalidOperationException("不存在指定的键");
                }

                _items[index].Delete(key);
            }

            public bool Find(TKey key, out TValue value)
            {
                value = default(TValue);

                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    return false;
                }

                Node<TKey, TValue> node;
                var finded = _items[index].Find(key, out  node);
                if (!finded)
                {
                    return false;
                }
                else
                {
                    value = node.Value;
                }

                return true;
            }

            private int HashToIndex(TKey key)
            {
                return key.GetHashCode() % _items.Length;
            }
        }
    }
}
